public class Rob {
    // 打家劫舍
    // https://leetcode.cn/problems/house-robber/?envType=study-plan-v2&envId=top-100-liked
    public int rob(int[] nums) {
        // 状态表示
        // f[i]表示第i个房子偷时候的最高金额
        // g[i]表示第i个房子不偷时候的最高金额
        // 状态转移方程
        // f[i] = max(max(f[i-2], g[i-2]), g[i-1]) + nums[i];
        // g[i] = max(max(f[i-1], g[i-1]), f[i-2])
        int len = nums.length;
        int[] f = new int[len+2];
        int[] g = new int[len+2];
        for (int i = 2; i < len+2; i++) {
            f[i] = Math.max(Math.max(f[i-2], g[i-2]), g[i-1]) + nums[i-2];
            g[i] = Math.max(Math.max(f[i-1], g[i-1]), f[i-2]);
        }
        return Math.max(f[len+1], g[len+1]);
    }
}
